#include <vector>
#include <iostream>

using namespace std;

/*
Bessie 都需要取换零钱的机器去换零钱。[10, 50, 100, 500]，机器使用的每一种面额的硬币数量是不限制的。
为了节约硬币，

机器最多一次只能兑换出 15 枚硬币。1000，机器不会给它 100 个 10 元。

编写一个函数，计算一下 Bessie 换 1000 元，究竟能在这个机器上得到多少种不同的硬币组合。

500 + 500
500 + 100 * 4
500 + 100 * 3 + 50 * 2
500 + 100 * 2 + 50 * 4
*/

// 10, 50, 100, 500, 最后一个元素的后一个位置
//                  ^end
// 读数组的元素两种方法：
// 1. 基于数字的位置 coins[0], coins[1], ... , coins[3]
// 2. 基于迭代器的位置 *coins.begin(), *(coins.begin() + 1), ..., *(coins.end() - 1)
int makingChange(int amount, int limit, vector<int> coins) {
  int coin = *(coins.end() - 1);
  coins.pop_back();
  int result = 0;

  if (coins.size() == 0) {
    // coin 是最后一个可用的面额
    if (amount / coin <= limit && amount % coin == 0) {
      return 1;
    }
    else {
      return 0;
    }
  }
  else {
    int branches = amount / coin + 1;
    for (int i = 0; i < branches; ++i) {
      result += makingChange(amount - i * coin, limit - i, coins);
    }
  }
  
  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << makingChange(1000, 15, {10, 50, 100, 500}) << endl;
  return 0;
}
